import math
import random

    
class GridDensityEstimator:
    """Determines a density of a set of points using a hash grid.
    Supports incremental addition of points"""
    def __init__(self,width=0.1):
        self.points = {}
        self.width = width

    def index(self,point):
        if isinstance(self.width,(tuple,list)):
            return tuple(int(math.floor(float(x)/w)) for (x,w) in zip(point,self.width))
        else:
            return tuple(int(math.floor(float(x)/self.width)) for x in point)

    def add(self,newPoint,id):
        index = self.index(newPoint)
        self.points.setdefault(index,[]).append((newPoint,id))

    def remove(self,point,id):
        index = self.index(point)
        try:
            delindex = (i for (i,p) in enumerate(self.points[index]) if p[1]==id).next()
            del self.points[index][delindex]
        except StopIteration:
            print 'Warning, point',point,'cannot be removed'

    def sample(self):
        return random.choice(random.choice(self.points))
